# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


from typing import List


# todo 关于二叉树的遍历，递归方式很好写，而迭代的方式不太好想，其实迭代思想也是基于递归
# 我们可以从递归来思考迭代。递归是把每一步的入栈出栈操作交给了计算机
# 迭代则是让我们自己扮演计算的角色，管理每一步的入栈出栈操作


class Solution:
    inorder_res = []

    """
    仔细观察每一步的递归。实际上是一直遍历左子树，当左子树遍历完成以后，然后访问当前根节点的值，最后 重复访问左子树的操作来 访问右子树
    所以在写迭代方法的时候，则是先遍历左子树，直到左子树为空，遍历的过程中依次入栈。当左子树空的时候，弹出栈顶元素（相当于左边的递归结束了）
    """

    def inorderRecursive(self, root: TreeNode):
        if root:
            self.inorderRecursive(root.left)
            self.inorder_res.append(root.val)
            self.inorderRecursive(root.right)

    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        curr = root
        stack.append(curr)
        while curr or len(stack) > 0:
            while curr.left:
                curr = curr.left
                stack.append(curr)

            node = stack.pop()
            res.append(node.val)
            curr = node.right

        return res
